package com.way.demo.sort;

import java.util.Arrays;

/**
 * @author lipingwei
 * @create 2023-03-06 22:45
 *   //归并排序
 */
public class MergeSort {
    public static void main(String[] args) {

         int[] arr={8,4,5,7,1,4,6,2};
         int[] tmp = new int[arr.length];
         mergeSort(0,arr.length-1,arr,tmp);
        System.out.println(Arrays.toString(arr));

    }

    //分的过程：

    public static void mergeSort(int left , int right, int[] arr, int[] tmp){
               if(left<right){
                   int mid =(left+right)/2;
                   //向左递归进行分解
                   mergeSort(left,mid,arr,tmp);
                   //向右递归进行分解
                   mergeSort(mid+1,right,arr,tmp);

                   //合并
                   merge(arr,left,mid,right,tmp);
               }

    }









    //先写合并的方法

    public static void merge(int[] arr, int left,int mid, int right,int[] temp){
        int i = left ;// 左边有序序列初始化
        int j= mid + 1; //初始化j,右边有序序列初始化索引
        int t =0;  //临时数据

        //先把左右两边的有序数据按照规填充到temp数组
        //的有序序列，有一遍处理完为止；
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        //左边的数据有剩余，全部放入临时数组

       while (i<=mid){
            temp[t]=arr[i];
            t++;
            i++;

        }
        while (j<=right){
            temp[t]=arr[j];
            t++;
            j++;

        }

         //临时数组的数据 拷贝到 原来数组
        t=0;
        int tempLeft=left;
        while(tempLeft<=right){
            arr[tempLeft]=temp[t];
            t++;
            tempLeft++;

        }

    }

}
